# 作者：石吴震
# 2025年01月08日12时01分39秒
# 474160957@qq.com

import random
import time
import sys
sys.setrecursionlimit(1000000)  # 设置递归深度

class Sort:
    def __init__(self, n):
        """
        n: 待排序的数组长度
        :param n:
        """
        self.len=n
        self.arr = [0]*n
        self.random_data()
    def random_data(self):
        for i in range(self.len):
            self.arr[i]=random.randint(0,99)

    def quick_sort(self, left, right):
        if left < right:
            m = self.partition(left, right)
            self.quick_sort(left, m-1)     # 左边
            self.quick_sort(m+1, right)    # 右边

    def partition(self, left, right):
        arr = self.arr
        k=i=left
        random_index=random.randint(left,right) # 减小出现最坏时间复杂度的可能性
        arr[right],arr[random_index]=arr[random_index],arr[right]
        for i in range(left,right):
            if arr[i]<arr[right]:
                arr[k],arr[i]=arr[i],arr[k]
                k+=1
        arr[k],arr[right]=arr[right],arr[k]
        return k

    def adjust_max_heap(self, pre,len):
        """
        调整为大根堆
        :param pre:
        :param len:
        :return:
        """

        dad=pre
        son=2*pre+1
        while son<len:
            if son+1<len and self.arr[son]<self.arr[son+1]:
                son+=1
            if self.arr[son]>self.arr[dad]:
                self.arr[son],self.arr[dad]=self.arr[dad],self.arr[son]
                dad=son
                son=2*son+1
            else:
                break

    def heap_sort(self):
        """
        交换首尾并调整堆
        :return:
        """
        arr=self.arr

        for i in range(self.len//2-1,-1,-1): #range左闭右开
            self.adjust_max_heap(i,self.len)
        arr[0],arr[self.len-1]=arr[self.len-1],arr[0]
        for i in range(self.len-1,1,-1):
            self.adjust_max_heap(0,i)
            arr[0],arr[i-1]=arr[i-1],arr[0]

    def test_time_use(self,sort_func,*args,**kwargs):
        """
        回调函数，测试排序算法的时间复杂度
        :param sort_func:
        :param args:
        :param kwargs:
        :return:
        """
        start=time.time()
        sort_func(*args,**kwargs)
        end=time.time()
        print(f"程序执行了{end-start}秒")

if __name__ == '__main__':
    count=100000
    my_sort=Sort(count)
    # print(my_sort.arr)
    # my_sort.quick_sort(0,count-1)
    # print(my_sort.arr)
    # my_sort.heap_sort()
    # print(my_sort.arr)
    my_sort.test_time_use(my_sort.quick_sort,0,count-1)
    my_sort.test_time_use(my_sort.heap_sort)